//A tree is an undirected graph in which any two vertices are connected by 
//exactly one path. In other words, any connected graph without simple cycles is a 
//tree. 
//
// Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 
//edges where edges[i] = [ai, bi] indicates that there is an undirected edge between 
//the two nodes ai and bi in the tree, you can choose any node of the tree as the 
//root. When you select a node x as the root, the result tree has height h. Among 
//all possible rooted trees, those with minimum height (i.e. min(h)) are called 
//minimum height trees (MHTs). 
//
// Return a list of all MHTs' root labels. You can return the answer in any 
//order. 
//
// The height of a rooted tree is the number of edges on the longest downward
//path between the root and a leaf. 
//
// 
// Example 1: 
//
// 
//Input: n = 4, edges = [[1,0],[1,2],[1,3]]
//Output: [1]
//Explanation: As shown, the height of the tree is 1 when the root is the node 
//with label 1 which is the only MHT.
// 
//
// Example 2: 
//
// 
//Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
//Output: [3,4]
// 
//
// Example 3: 
//
// 
//Input: n = 1, edges = []
//Output: [0]
// 
//
// Example 4: 
//
// 
//Input: n = 2, edges = [[0,1]]
//Output: [0,1]
// 
//
// 
// Constraints: 
//
// 
// 1 <= n <= 2 * 10⁴ 
// edges.length == n - 1 
// 0 <= ai, bi < n 
// ai != bi 
// All the pairs (ai, bi) are distinct. 
// The given input is guaranteed to be a tree and there will be no repeated 
//edges. 
// 
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 396 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class P310MinimumHeightTrees {
    public static void main(String[] args) {
        Solution solution = new P310MinimumHeightTrees().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 首先，我们看了样例，发现这个树并不是二叉树，是多叉树。
         * 然后，我们可能想到的解法是：根据题目的意思，就挨个节点遍历bfs，统计下每个节点的高度，然后用map存储起来，后面查询这个高度的集合里最小的就可以了。
         * 但是这样会超时的。
         * 于是我们看图（题目介绍里面的图）分析一下，发现，越是靠里面的节点越有可能是最小高度树。
         * 所以，我们可以这样想，我们可以倒着来。
         * 我们从边缘开始，先找到所有出度为1的节点，然后把所有出度为1的节点进队列，然后不断地bfs，最后找到的就是两边同时向中间靠近的节点，那么这个中间节点就相当于把整个距离二分了，那么它当然就是到两边距离最小的点啦，也就是到其他叶子节点最近的节点了。
         * 然后，就可以写代码了。
         *
         * @param numCourses
         * @param prerequisites
         * @return
         */
        public List<Integer> findMinHeightTrees(int numCourses, int[][] prerequisites) {
            /*如果只有一个节点，那么他就是最小高度树*/
            List<Integer> res = new ArrayList<>();
            if (numCourses == 1) {
                res.add(0);
                return res;
            }
            int[] degree = new int[numCourses];
            List<List<Integer>> adjacency = new ArrayList<>();
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                adjacency.add(new ArrayList<>());
            }
            // Get the indegree and adjacency of every course.
            for (int[] cp : prerequisites) {
                degree[cp[0]]++;
                degree[cp[1]]++;
                adjacency.get(cp[1]).add(cp[0]);
                adjacency.get(cp[0]).add(cp[1]);
            }
            // Get all the courses with the indegree of 1.
            for (int i = 0; i < numCourses; i++) {
                if (degree[i] == 1) {
                    queue.add(i);
                }
            }
            /*循环条件当然是经典的不空判断*/
            while (!queue.isEmpty()) {
                res = new ArrayList<>();/*这个地方注意，我们每层循环都要new一个新的结果集合，
            这样最后保存的就是最终的最小高度树了*/
                int size = queue.size();/*这是每一层的节点的数量*/
                for (int i = 0; i < size; i++) {
                    int cur = queue.poll();
                    res.add(cur);/*把当前节点加入结果集，不要有疑问，为什么当前只是叶子节点为什么要加入结果集呢?
                因为我们每次循环都会新建一个list，所以最后保存的就是最后一个状态下的叶子节点，
                这也是很多题解里面所说的剪掉叶子节点的部分，你可以想象一下图，每层遍历完，
                都会把该层（也就是叶子节点层）这一层从队列中移除掉，
                不就相当于把原来的图给剪掉一圈叶子节点，形成一个缩小的新的图吗*/
                    List<Integer> neighbors = adjacency.get(cur);
                    /*这里就是经典的bfs了，把当前节点的相邻接点都拿出来，
                     * 把它们的出度都减1，因为当前节点已经不存在了，所以，
                     * 它的相邻节点们就有可能变成叶子节点*/
                    for (int neighbor : neighbors) {
                        degree[neighbor]--;
                        if (degree[neighbor] == 1) {
                            /*如果是叶子节点我们就入队*/
                            queue.offer(neighbor);
                        }
                    }
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}